#pragma once
#include<iostream>
#include <vector>
#include <thread>
#include <time.h>
#include <assert.h>
#include <mutex>
#include<algorithm>

using std::cout;
using std::endl;

#ifdef _WIN64                        // x64同时定义_win32和_win64
typedef unsigned long long PAGE_ID;  // 2^64/2^13 =2^51 size_t 不够用
#elif _WIN32
typedef size_t PAGE_ID;
#else
// linux
#endif

#ifdef _WIN32
#include<windows.h>
#else
// Linux下mmap
#include <sys/mman.h>
#endif

inline static void* SystemAlloc(size_t kpage)  
{
#ifdef _WIN32
    // Windows下的VirtualAlloc分配大小单位为字节(其中一页为8k)
    void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE,
        PAGE_READWRITE);
#else
    // linux下brk mmap
    void* ptr = mmap(0, kpage << 13, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
    if (ptr == nullptr)
        throw std::bad_alloc();
    return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // linux下sbrk unmmap
    
#endif
    
}


// 小于等于MAX_BYTES的内存申请走thread cache申请
static const size_t MAX_BYTES = 256 * 1024;   // 256KB

// thread cache和central cache自由链表哈希桶的个数
static const size_t NFREELISTS = 208;

static const size_t PAGES = 129;

static const size_t PAGE_SHIFT = 13;  // 一页为8K字节

static void*& NextObj(void* obj) 
{
    return (*(void**)obj);
}

// 自由链表管理切分好的小内存块
class FreeList
{
public:
    // 将释放的对象头插到自由链表中
    void Push(void* obj) 
    {
        assert(obj);

        NextObj(obj)=_freeList;
        _freeList = obj;
        ++_size;
    }
    void PushRange(void* start, void* end,size_t n)
    {
        assert(start);
        assert(end);
        NextObj(end) = _freeList;
        _freeList = start;
        _size+=n;
    }
    // 从自由链表头部取出一个对象
    void* Pop()
    {
        assert(_freeList);
        // 头删
        void* obj = _freeList;
        _freeList = NextObj(_freeList);
        --_size;
        return obj;
    }
    void PopRange(void*& start,void*& end,size_t n)
    {
        assert(n <= _size);

        // 头删
        start = _freeList;
        end = start;
        for (size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }
        _freeList = NextObj(end); // 自由链表指向end的下一个对象
        NextObj(end) = nullptr; // 取出的一段链表的尾节点的next置空
        _size -= n;
    }
    bool Empty() 
    {
        return _freeList == nullptr;
    }

    size_t& MaxSize()
    {
        return _maxSize;
    }
    size_t Size() {
        return _size;
    }
private:
    // 自由链表头指针
    void* _freeList = nullptr;
    size_t _maxSize = 1;
    size_t _size = 0;
};

// 计算对象大小的映射关系
class SizeClass
{
public:
    // 不同对齐数，对应不同的对象大小
    // 整体控制在最多10%左右的内碎片浪费
    // [1,128]                    8字节对齐     freelist[0,16)   
    // [128+1,1024]              16字节对齐     freelist[16,72)  15/(129+15)=0.104
    // [1024+1,8*1024]           128字节对齐    freelist[72,128) 127/(1025+127)=0.110
    // [8*1024+1,64*1024]        1024字节对齐   freelist[128,184)
    // [64*1024+1,256*1024]      8*1024字节对齐 freelist[184,208)

    // 使用位运算的方式计算对齐数，比取模的方式更快
    static inline size_t _RoundUp(size_t bytes, size_t alignNum)
    {
        return (bytes + alignNum - 1) & ~(alignNum - 1);
    }

    // 获取向上取整的字节数
    static inline size_t RoundUp(size_t bytes)
    {
        if (bytes <= 128)
        {
            return _RoundUp(bytes, 8);
        }
        else if (bytes <= 1024)
        {
            return _RoundUp(bytes, 16);
        }
        else if (bytes <= 8 * 1024)
        {
            return _RoundUp(bytes, 128);
        }
        else if (bytes <= 64 * 1024)
        {
            return _RoundUp(bytes, 1024);
        }
        else if (bytes <= 256 * 1024)
        {
            return _RoundUp(bytes, 8 * 1024);
        }
        else
        {
            //assert(false);
            //return -1;
            return _RoundUp(bytes, 1 << PAGE_SHIFT);
        }
    }

    // 计算映射的哪一个自由链表桶
    static inline size_t _Index(size_t bytes, size_t alignShift)
    {
        return ((bytes + (1 << alignShift) - 1) >> alignShift) - 1;
    }

    // 获取对应哈希桶的下标
    static inline size_t Index(size_t bytes)
    {
        // 每个区间有多少个链
        static size_t groupArray[4] = { 16, 56, 56, 56 };
        if (bytes <= 128)
        {
            return _Index(bytes, 3);
        }
        else if (bytes <= 1024)
        {
            return _Index(bytes - 128, 4) + groupArray[0];
        }
        else if (bytes <= 8 * 1024)
        {
            return _Index(bytes - 1024, 7) + groupArray[0] + groupArray[1];
        }
        else if (bytes <= 64 * 1024)
        {
            return _Index(bytes - 8 * 1024, 10) + groupArray[0] + groupArray[1] + groupArray[2];
        }
        else if (bytes <= 256 * 1024)
        {
            return _Index(bytes - 64 * 1024, 13) + groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3];
        }
        else
        {
            assert(false);
            return -1;
        }
    }

    // 一次从中心缓存获取多少个
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);

        // [2,512] 一次批量移动多少个对象的(慢启动)上限值
        int num = MAX_BYTES / size;
        if (num < 2)
            num = 2;
        if (num > 512)
            num = 512;
        return num;
    }

    // 计算一次向系统获取几个页
    static size_t NumMovePage(size_t size)
    {
        assert(size > 0);
        size_t num = NumMoveSize(size);
        size_t npage = num * size;

        npage >>= PAGE_SHIFT;
        if (npage == 0)
            npage = 1;

        return npage;
    }
};

// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t  _n = 0;      // 页的数量

    Span* _next = nullptr;    // 双向链表
    Span* _prev = nullptr;

    size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数
    size_t _objSize = 0;  //切好小块内存的大小
    void* _freeList = nullptr;  // 切好的小块内存的自由链表

    bool _isUse = false;        // 是否在被使用
};

// 当某个span的_useCount计数为0时，说明当前span切分出去的内存全部回收了，也就可以合并了

// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }
    Span* Begin()
    {
        return _head->_next;
    }
    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;

        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }
    void Erase(Span* pos)
    {
        assert(pos);
        assert(pos != _head); // 不能删除哨兵位

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    bool Empty()
    {
        return _head->_next == _head;
    }

    Span* PopFront()
    {
        Span* front = _head->_next;
        Erase(front);
        return front;
    }

    void PushFront(Span* span)
    {
        Insert(Begin(), span);
    }
private:
    Span* _head;
public:
    std::mutex _mtx; // 桶锁
};
// 从链表中去掉span，不是delete，只是从链表中移除


